<TITLE>prob015: Schur's lemma</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob015: Schur's lemma</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>
The problem is to put n balls labelled {1,...n} into 3 boxes so 
that for any triple of balls (x,y,z) with x+y=z, not all are in
the same box. This has a solution iff n < 14. 

<P>
The problem can be
formulated as an 0-1 problem using the variables, M_ij (i in [1,n], 
j in [1,3]) with M_ij true iff ball i is in box j. The constraints are 
that a ball must be in exactly one box,
 M_i1 + M_i2 + M_i3 = 1   for all i in [1,n].
And for each x+y=z and j in [1,3],
 not (M_xj and M_yj and M_zj).
This converts to,
 (1-M_xj) + (1-M_yj) + (1-M_zj) >= 1
 or,
 M_xj + M_yj + M_zj <= 2.

<P>
One natural generalization is to consider partitioning
into k boxes (for k>3).

</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


